//package work.rightAnswer;
//
//class Solution_918 {
//    public int maxSubarraySumCircular(int[] nums) {
//        //并不是所有题目都能用贪心算法，不要上来就是局部-》整体这个思路。
//        //一开始应该是分析题目
//        //本题求：环形子数组的最大和，先分析，结果可能是怎么样的 ：1.中间 2.左前缀与右后缀相加
//        //思路，用动态规划，记录下左前缀的最大值
//        //dp[i]含义：0-i下标时，以0开头的最大连续数组和
//        int[] maxLeft = new int[nums.length];
//        maxLeft[0] = nums[0];
//        int leftSum = nums[0];//0-i数组和
//        int midSum = nums[0];//0-i之间以i结尾的的最大数组和
//        int midMax = nums[0];//中间层最大子数组和
//        for (int i = 1; i < nums.length; i++) {
//            midSum = Math.max(nums[i],midSum+nums[i]);
//            midMax = Math.max(midMax,midSum);
//            leftSum+=nums[i];
//            maxLeft[i] = Math.max(maxLeft[i-1],leftSum);
//        }
//
//
//        int rightSum = 0;
//        int res = midMax;
//        //从右到左遍后缀，固定后缀，选择最大前缀
//        for (int i = nums.length-1; i >0 ; i--) {
//            rightSum += nums[i];
//            res = Math.max(res,rightSum+maxLeft[i-1]);
//        }
//        return res;
//    }
//}